Shor 算法

阐述

问题

给定合数 $N$，找到 $1<p<N$ 使得 $N/p\in\mathbb Z^+$。

经典部分

首先确定 $N$ 不是偶数且不是任何正整数的幂。

1. 随机选取 $1<a<N$，计算 $\operatorname{gcd}(a,N)$，如果它不为 1，则问题解决；
2. 寻找最小的正整数 $r$ 使得 $a^r\equiv 1\mod N$；
3. 如果 $r$ 是偶数且 $a^{r/2}\not\equiv -1\mod N$，则 $\operatorname{gcd}(a^{r/2}-1,N)$ 和 $\operatorname{gcd}(a^{r/2}+1,N)$ 都是 $N$ 的非平凡因子；
4. 否则返回步骤 1。

量子部分

解释

构造如下酉变换

$$U_{a}|y \quad(\bmod N)\rangle=|a y \quad(\bmod N)\rangle$$

它是可逆的，因为可以通过 Euclidean 算法找出 $a$ 的逆元。注意到它有如下形式的本征态（$k=0,\cdots,r-1$）

$$\left|\zeta_{k}\right\rangle=\frac{1}{r}\left(|1\rangle+e^{2 \pi i k / r}|a\rangle+e^{4 \pi i k / r}\left|a^{2}\right\rangle+\ldots e^{2 \pi(r-2) k / r}\left|a^{r-2}\right\rangle+e^{2 \pi(r-1) k / r}\left|a^{r-1}\right\rangle\right)$$

满足 $U_{a}\left|\zeta_{k}\right\rangle = e^{-2 \pi k / r}\left|\zeta_{k}\right\rangle$。若 $N$ 为 $L$-bit 数字，我们使用第一组寄存器长度为 $2L$，第二组为 $L$，则上述电路给出 $d/2^{2L}\approx k/r$ 对于某个未知的 $k$。由于 $k,r$ 最多为 $L$ 位，我们可以用连分数展开来获取 $r$。

实例

性质

相关内容

参考文献

• Shor's algorithm - Wikipedia